For any suggestions or feedback regarding these notes,

please contact Pragy Agarwal

k-Nearest Neighbor (k-NN) Queries

Imagine that you're building Zomato, and you've a table called restaurants that holds 100 million entries.

create table restaurants(id bigint primary key,

name varchar(50),

address varchar(200),

latitude real,

longitude real)

Assume that we also have the necessary indexes on the latitude and longitude columns.

Note: modern SQL databases like postgres support geolocation datatypes via extensions (eg, postgis)

Task

Given a user's geolocation (latitude, longitude), you have to find k nearby restaurants.

Attempt 1 - find closest k restaurants

select *,

((latitude - user_latitude) * (latitude - user_latitude)

+ (longitude - user_longitude) * (longitude - user_longitude)) as distance

from restaurants

order by distance asc

limit k

note: the formula used is the Euclidean Distance (two point distance) formula

Q: What is the time complexity of the above query, assuming that the table has N rows, and we've indexes on the latitude & longitude columns?

O(N log k)

Even though we have the indexes, we cannot use them

because we're sorting on the distance, and not the latitude/longitude
this will be a linear scan through the entire table

Returning top k

log(k) for the min/max heap

Given an unsorted array of n elements, find the top k ⇒ this takes O(n log k) time

Attempt 1.1 - find all restaurants within a circle

select *,

((latitude - user_latitude) * (latitude - user_latitude)

+ (longitude - user_longitude) * (longitude - user_longitude)) as distance

from restaurants

where distance <= R

limit k

Q: Time Complexity?

O(N)

No sorting/heap needed now.

But we still have to perform a linear scan through the entire table – because the distance formula is complex, and the database cannot use the index to optimize this formula.

A database index is just a sorted array / BBST

You can do lowerbound/upperbound queries (binary search) using an index.

Circle formulas are complex. Rectangles are simpler!

Attempt 2 - find all restaurants within a square

select *

from restaurants

where user_latitude between ( latitude - L) and ( latitude + L)

and user_longitude between (longitude - L) and (longitude + L)

limit k

Q: Time Complexity, assuming that we've index on both latitude and longitude columns?

O(log N)

still O(N) worst case! Because you can only use 1 index at a time.

Database will use the index on latitude to get all the restaurants in the blue region
Then, it will use the index to get all the restaurants in the yellow region
DB will take intersection of the two sets

We are still searching through a much larger region than what we actually desire!

Note: this query is better than the circle query, but still not perfect!

Wait, really? What if we also had a multi-column indices?

Single column indices

create index idx_lat on restaurants(latitude);

create index idx_lon on restaurants(longitude);

Multicolumn (composite/joint) indices

create index idx_lat_lon on restaurants(latitude, longitude);

create index idx_lon_lat on restaurants(longitude, latitude);

Unfortunately, even after having multi-column indexes, the search will still remain the exact same! (we will still scan through the blue+yellow region, and then take intersection)

Why though?

Multi-column indexes can perform range queries only on last column!

can do efficiently O(log N)

exact queries on any columns

latitude = X
longitude = Y
latitude = X and longitude = Y

range queries on last column (exact queries on all previous columns)

latitude = X and longitude between Y1 and Y2

range queries on a specific column, and include everything in all the other columns to the right

latitude between X1 and X2, and the longitude can be anything

can NOT do efficiently

range queries on both columns

latitude between X1 and X2 and longitude between Y1 and Y2

Demo - why Composite Index can't do multi-column range queries

Attempt 3 - fixed grid

First break the world into a fixed sized grid
For each restaurant, add the cell_id in the restaurants table

alter table restaurants add cell_id integer;

we will calculate the cell_id of each restaurant based on its geolocation (lat/lon)
we will place an index on the cell_id column

Given the user's geolocation, get the user's cell id

get_cell_id(user_latitude, user_longitude)

Find all restaurants within that cell

select *

from restaurants

where cell_id = get_cell_id(user_latitude, user_longitude)

Q: Time Complexity, assuming that we've index on cell_id?

finally, this query will achieve our desired complexity!

O(log N)

Issue

Density of restaurants changes depending on the location.

Some cells have lots of restaurants, some cells have no restaurants.

So if the user happens to fall in a low density region, we will not be able to find sufficient restaurants for this user.

One approach to fixing this could be to simply expand the search to the nearby cells

select * from restaurants

where cell_id in ( 18, 17, 19, 5, 6, .. ) (surrounding cells)

We don't want a fixed sized grid - we want a Dynamic Sized Grid!

We need a grid that considers the density of the region.

Spatial Index - QuadTrees

Note: There are many other types of spatial indexes.

Quad Trees (2d spatial index)
k-D Trees (for higher dimensions)
GiST
Geohash
dozens more!

Visualization: https://kshitijmishra23.github.io/interactive-quadtrees/

QuadTrees create a dynamic grid. The grid size is based on the density of the region.
2D index: index on two columns where you can do range queries on both the columns! (Spatial index)

QuadTrees provide efficient range queries on 2 dimensions simultaneously!

Unlike regular B+tree indexes, which only work in 1 dimension, quad-trees work in 2 dimensions!

Intuition

Start with all restaurants in the root node
If the node contains more than M=10 restaurants, split the node into 4 equal quadrants
Recurse

M is a configurable parameter

Each node in the tree must be aware of its coordinates.

Please practice the QuadTree data structure: Construct Quad Tree - LeetCode

Pseudocode

class Restaurant:

id: int

latitude: float

longitude: float

# the rest of the info will be stored in the db table, and not in the quad tree

class QuadTree:

id: int

top, left, bottom, right: (float, float, float, float)

restaurants: list[Restaurant] # this will be populated

# only for leaf nodes

# it will be empty for intermediate nodes

children: list[QuadTree] # populated only for intermediate nodes

# it will be empty for leaf nodes

def find(self,

latitude: float,

longitude: float) -> list[Restaurant]:

"""given a user's location, finds the restaurants that

fall in the same cell as this location"""

if not ( self.left <= latitude < self.right \

and self.top <= longitude < self.bottom ):

return [] # user's location out of current node's bounds

if not self.children: # we're a leaf node

return self.restaurants

# recurse over children

for child in self.children:

restaurants = child.find(latitude, longitude)

if restaurants:

return restaurants

def insert(self, restaurant: Restaurant):

"""insert the restaurant"""

if not ( self.left <= restaurant.latitude <= self.right \

and self.top <= restaurant.longitude <= self.bottom ):

return # location out of current node's bounds

if not self.children: # we're a leaf node

self.restaurants.append(restaurant)

if len(self.restaurants) > SPLIT_THRESHOLD:

# create 4 new children

# with the appropriate coordinates

# move restaurants to children

...

return

# recurse over children

for child in self.children:

child.insert(restaurant)

def delete(self, restaurant: Restaurant):

"""delete the restaurant from the tree"""

# similar to insert

# find the node

# if leaf remove restaurant from the list

# if parent’s count < SPLIT_THRESHOLD, then go to parent

# and re-join children

# otherwise, recurse on our children

Note that

inserts can cause an existing leaf node to get split
deletes can cause an existing intermediate node to get merged.

Also note that a leaf node need not always contain M restaurants.

It is possible for a leaf node to be empty.

If a user happens to fall in a cell which doesn't contain any restaurants, how will we find the relevant restaurants?

expand the search to the parent node

easy - just go to the parent node, and find all restaurants within it (from all children)

expand the search to the neighboring nodes

much more complex - because neighboring nodes need not come from immediate parent
however, it can be done efficiently

If you find that situations like this are happening very frequently, then this simply means that you've a bad value of M - try to increase the split threshold

Time Complexity for QuadTree operations

O(log4 N) where N is the number of entries in the quadtree

Note that this is the average complexity of insert/delete/find

The worst case can be very bad up to O(N) because the tree can get skewed — but practically this is unlikely to happen.

Practically, the complexity still remains O(log4 N)

Storing a QuadTree

If we have 100 million restaurants, how large (in bytes) will the quadtree be?

class Restaurant:

id: int

latitude: float

longitude: float

# note that other details about the restaurant will not

# be stored within the quad tree

# they will be stored in the SQL table

class QuadTree:

id: int

top, left, bottom, right: (float, float, float, float)

restaurants: list[Restaurant]

children: list[QuadTree]

Number of nodes

Only the leaf nodes will store the restaurants. Intermediate nodes do NOT store the restaurants.

(overestimating the number of nodes)

Assume each leaf node stores 1 restaurant on average..

some leaf nodes have a lot of restaurants – up to M=10
some leaf nodes are completely empty

But we can assume that each leaf has at least 1 restaurant on average.

Total nodes

Total Space

We will need around 12 GB to store a quadtree with 100 million restaurants

Do we need Sharding?

Absolutely not!

11 GB is actually small enough to fit in the RAM

Typical production servers can have up to 64GB of RAM easily..

A single server can hold the entire quad tree to store 100 million nodes.

Because the complexity of operations is O(log4 N) and all operations are happening purely in the RAM, the single server will be able to handle 10,000 - 100,000 operations / second!